package com.gao.util;

/**
 * @author gao
 * @date 2023/08/10 09:52:19
 */
public class SingleLinkedList<T> implements List<T> {
    private Node head, tail;
    private int size;

    public SingleLinkedList() {
    }

    private SingleLinkedList(Node head) {
        this.head = head;
    }

    public boolean add(T val) {
        Node<T> node = new Node<>(val);
        if (head == null) {
            head = tail = node;
        }
        tail.next = node;
        tail = tail.next;
        size++;
        return true;
    }

    @Override
    public T set(int index, T val) {
        Node<T> curr = head;
        int k = 0;
        while (k < index) {
            curr = curr.next;
            k++;
        }

        return null;
    }

    public boolean del(T val) {
        Node<T> node = findNodeByVal(val);
        if (node == null) {
            return false;
        }
        Node prev = findPrevNodeByVal(val);
        if (prev == null) {
            // 如果prev是null，说名要删除的是头节点
            Node h = head;
            head = head.next;
            h.next = h;
            return true;
        }
        Node next = node.next;

        prev.next = next;
        node.next = node;

        size--;
        return true;

    }

    @Override
    public T del(int index) {
        rangeCheck(index);
        Node<T> curr = findNodeByIndex(index);
        Node<T> prev = findPrevNodeByIndex(index);
        if (prev == null) {
            // 如果prev是null，说名要删除的是头节点
            Node<T> h = head;
            head = head.next;
            h.next = h;
            return h.val;
        }
        Node<T> next = curr.next;

        prev.next = next;
        curr.next = curr;

        return curr.val;
    }

    @Override
    public T get(int index) {
        rangeCheck(index);
        Node<T> curr = head;
        int k = 0;
        while (k < index) {
            curr = curr.next;
            k++;
        }
        return curr.val;
    }

    private Node<T> findPrevNodeByVal(T val) {
        Node<T> curr = head;
        Node<T> prev = null;
        while (curr != null && curr.val != val) {
            prev = curr;
            curr = curr.next;
        }
        return prev;
    }

    private Node<T> findNodeByVal(T val) {
        Node<T> curr = head;
        while (curr != null && curr.val != val) {
            curr = curr.next;
        }
        return curr;
    }

    private Node<T> findNodeByIndex(int index) {
        rangeCheck(index);
        Node<T> curr = head;
        int k = 0;
        while (k < index) {
            curr = curr.next;
            k++;
        }
        return curr;
    }

    private Node<T> findPrevNodeByIndex(int index) {
        rangeCheck(index);
        Node<T> prev = null;
        Node<T> curr = head;
        int k = 0;
        while (k < index) {
            prev = curr;
            curr = curr.next;
            k++;
        }
        return prev;
    }

    private void rangeCheck(int index) {
        if (index < 0 || index > size - 1) {
            throw new RuntimeException("下标越界：" + index);
        }
    }

    public Iterator<T> iterator() {
        return new LinkListIterator<T>();
    }

    @Override
    public void reverse() {
        this.reverse(0, size - 1);
    }

    @Override
    public void reverseInGroup(int k) {
        if (k == 0) {
            return;
        }
        Node<?> dummy = new Node<>(null);
        dummy.next = head;
        Node<?> beforeStart = dummy;

        int start = 0;
        while (start + k < size && beforeStart.next != null) {
            Node<?> curr = beforeStart.next;
            int t = 1;
            while (t < k && curr.next != null) {
                Node<?> post = curr.next;
                curr.next = post.next;
                post.next = beforeStart.next;
                beforeStart.next = post;
                t++;
            }
            start += k;
            beforeStart = curr;
        }
        head = dummy.next;
    }

    @Override
    public void reverse(int start, int end) {
        rangeCheck(start);
        rangeCheck(end);
        if (start > end) {
            throw new RuntimeException("start不能比end大：start = " + start + ", end =" + end);
        }

        Node<?> dummy = new Node<>(null);
        dummy.next = head;

        Node<?> beforeStart = null;
        Node<?> curr = null;

        if (start == 0) {
            beforeStart = dummy;
        } else {
            beforeStart = findPrevNodeByIndex(start);
        }
        curr = beforeStart.next;

        int reverseTimes = end - start;
        int k = 0;
        while (k < reverseTimes && curr.next != null) {
            Node post = curr.next;
            curr.next = post.next;
            post.next = beforeStart.next;
            beforeStart.next = post;
            k++;
        }
        if (start == 0) {
            head = dummy.next;
        }
        // for GC
        dummy = dummy.next = null;
    }


    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 合并两个有序单向链表
     *
     * @param list
     */
    public void merge(SingleLinkedList<T> list) {
        Node<T> h = head;
        Node<T> h2 = list.head;

        Node<T> dummy = new Node(null);
        Node<T> pre = dummy;

        while (h != null && h2 != null) {
            if (!(h.val instanceof Comparable)) {
                throw new RuntimeException(h.val + "没有实现Comparable接口，无法比较");
            }
            if (!(h2.val instanceof Comparable)) {
                throw new RuntimeException(h2.val + "没有实现Comparable接口，无法比较");
            }
            Comparable<T> c = (Comparable<T>) h.val;
            Comparable<T> c2 = (Comparable<T>) h2.val;

            if (c.compareTo((T) c2) <= 0) {
                pre.next = h;
                h = h.next;
            } else {
                pre.next = h2;
                h2 = h2.next;
            }

            pre = pre.next;
        }

        if (h != null) {
            pre.next = h;
        } else {
            pre.next = h2;
        }

        head = dummy.next;
    }

    private class LinkListIterator<T> implements Iterator<T> {
        private Node<T> curr = head;

        @Override
        public boolean hasNext() {
            return curr != null;
        }

        @Override
        public T next() {
            T val = curr.val;
            curr = curr.next;
            return val;
        }
    }


    public class Node<T> {
        private T val;
        private Node next;

        public Node(T val) {
            this.val = val;
        }

        public T getVal() {
            return val;
        }

        public void setVal(T val) {
            this.val = val;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }

        @Override
        public String toString() {
            return "Node{" + "val=" + val + '}';
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Iterator<T> it = iterator();
        while (it.hasNext()) {
            T next = it.next();
            sb.append(next);
            sb.append(",");
        }
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }


}
